package BinaryTreeCameras_968;

public class Solution {
    public int minCameraCover(TreeNode root) {
        Info info = process(root);
        return !info.hasMonitor ? info.cameras + 1 : info.cameras;
    }


    private Info process(TreeNode node) {
        if (node == null) {
            return new Info(true, false, 0);
        }

        Info leftInfo = process(node.left);
        Info rightInfo = process(node.right);
        //左孩子或者右边孩子没被监视，这里必须安装摄像头
        if (!leftInfo.hasMonitor || !rightInfo.hasMonitor) {
            return new Info(true, true, leftInfo.cameras + rightInfo.cameras + 1);
        }
        // 到这里就可以确保左右孩子都已经被监视了。

        //如果左右孩子其中有一个有摄像头，我这里都可以被监视，且不要摄像头
        if (leftInfo.hasCameras || rightInfo.hasCameras) {
            return new Info(true, false, leftInfo.cameras + rightInfo.cameras);
        }
        //这里就是左右孩子都没有摄像头，我也没有被监视。交给父处理
        return new Info(false, false, leftInfo.cameras + rightInfo.cameras);
    }
}


class Info {

    boolean hasMonitor;

    boolean hasCameras;
    int cameras;


    public Info(boolean hasMonitor, boolean hasCameras, int cameras) {
        this.hasMonitor = hasMonitor;
        this.hasCameras = hasCameras;
        this.cameras = cameras;
    }
}
